#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>

using namespace std;

struct Node {
    int vertex;
    int weight;
    Node(int v, int w) : vertex(v), weight(w) {}
    bool operator<(const Node& other) const {
        return weight > other.weight;
    }
};

/**
 * Dijkstra算法实现函数
 * 
 * @param graph 图的邻接表表示，其中graph[i]是一个包含一对<int, int>的vector，表示顶点i到其他顶点的边和权重
 * @param src 起始顶点的索引
 * @param V 图中顶点的数量
 * 
 * 此函数使用优先队列来实现Dijkstra算法，计算起始顶点到图中其他所有顶点的最短路径
 */
void dijkstra(vector<vector<pair<int, int>>>& graph, int src, int V) {
    // 初始化距离数组，所有顶点的距离初始值设为无穷大
    vector<int> dist(V, INT_MAX);
    // 定义一个优先队列，用于存储待处理的顶点，队列头部是距离最小的顶点
    priority_queue<Node> pq;

    // 设置起始顶点的距离为0，并将其加入优先队列
    dist[src] = 0;
    pq.push(Node(src, 0));

    // 当优先队列不为空时，循环处理队列中的顶点
    while (!pq.empty()) {
        // 获取并移除优先队列的头部顶点
        Node top = pq.top();
        pq.pop();

        // 获取当前处理的顶点索引
        int u = top.vertex;

        // 遍历当前顶点的所有邻居
        for (auto& neighbor : graph[u]) {
            // 获取邻居顶点的索引和到该邻居的边的权重
            int v = neighbor.first;
            int weight = neighbor.second;

            // 如果通过当前顶点到达邻居顶点的路径更短，则更新邻居顶点的距离并将其加入优先队列
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(Node(v, dist[v]));
            }
        }
    }

    // 输出所有顶点到起始顶点的最短距离
    cout << "Vertex\tDistance from Source" << endl;
    for (int i = 0; i < V; i++) {
        cout << i << "\t" << dist[i] << endl;
    }
}